/*
 * @lc app=leetcode.cn id=2121 lang=cpp
 *
 * [2121] 相同元素的间隔之和
 */

// @lc code=start
class Solution
{
public:
    vector<long long> getDistances(vector<int> &arr)
    {
        int n = arr.size();
        vector<int> idxs(n);
        // 初始化下标数组
        for (int i = 0; i < n; i++)
        {
            idxs[i] = i;
        }
        // 排序
        sort(idxs.begin(), idxs.end(), [&](int i, int j) -> bool
             {
                if (arr[i] != arr[j]) {
                    return arr[i] < arr[j];
                }
                return i < j; });
        // 初始化答案数组
        vector<long long> ans(n);
        // 计算答案
        for (int i = 0, j = 0; i < n; i = j + 1)
        {
            // [i ,j] 是相同数字的下标区间
            j = i;
            while (j + 1 < n && arr[idxs[j + 1]] == arr[idxs[i]])
            {
                j++;
            }
            // k 位置前后的前缀和
            long long sum_pre = 0, sum_next = 0;
            for (int k = i; k <= j; k++)
            {
                sum_next += idxs[k];
            }
            for (int k = i; k <= j; k++)
            {
                sum_next -= idxs[k];
                ans[idxs[k]] = (long long)(2 * k - i - j) * idxs[k] - sum_pre + sum_next;
                sum_pre += idxs[k];
            }
        }
        return ans;
    }
};
// @lc code=end
